§1.1 Field of the Invention
The present invention concerns matching an arbitrary-length bit string with one of a number of known arbitrary length bit strings. The present invention may be used for network intrusion detection and prevention. In particular, the present invention concerns a novel data structure namely, a trie bitmap content analyzer, which provides minimum perfect hashing functionality while supporting low-cost set membership queries. By using such a data structure, matching can be checked at high speed.
§1.2 Background Information
High-speed Network Intrusion Detection and Prevention Systems (“NIDPS”) have gained a lot of attention recently as part of the effort to keep up with the ever-increasing bandwidth requirement of today's networks. The most time-consuming task of NIDPS is Deep Packet Inspection (“DPI”). DPI also has applications in other networking areas, such as layer-7 switching, URL inspection, and spam, virus, and worm detection (C. Burns and D. Newman. (2006, January). Vendors choose to tout disparate application-acceleration techniques. Available: http://www.networkworld.com/reviews/2006/011606-wfe-features.html), (S. Singh, C. Estan, G. Varghese, and S. Savage, “Automated worm fingerprinting,” in Proc. of the ACM/USENIX Symposium on Operating System Design and Implementation, San Francisco, Calif., December 2004.). DPI is the task of searching for a static or dynamic set of strings within each incoming packet. In the NIDPS context, DPI searches for pre-defined attack signatures in the incoming packets so as to identify malicious content.
Unlike most network applications, such as IP lookup and packet classification, whose complexity is proportional to the packet rate in packets/sec, DPI's complexity is determined by the data rate in bytes/sec, making it computationally harder than other applications. DPI's complexity is also increased by the number and length of strings in the set (signatures). As a result, the issue of designing a DPI system that is scalable in processing speed independent of the string set remains a challenge. Moreover, the application may have a dynamic signature set that is updated when necessary. Although in NIDPS these updates are relatively infrequent, the need to easily update the NIDPS signature set when required is still a challenge and often creates conflicts when designing a high-speed system.
§1.2.1 Previous Approaches and Perceived Limitations of Such Approaches
Present software DPI methods are typically not scalable for high-speeds (SNORT, available at: http://www.snort.org) because general-purpose hardware running software DPI is intrinsically slow and has limited parallelism. Hence, only hardware approaches are discussed. Research to increase the DPI speed focuses on two aspects: (1) increasing the speed of unit inspection operation (i.e., operation for each byte of the incoming packet), and (2) reducing the number of DPI operations by identifying possible malicious packets at the early stages of the inspecting process, while passing most of the packets that are legitimate.
To increase the speed of detection, some approaches use external memory structures (F. Yu, T. Lakshman, and R. Katz, “Gigabit rate pattern-matching using tcam,” in Int. Conf. on Network Protocols (ICNP), Berlin, Germany, October 2004.), (H. Song and J. Lockwood, “Multi-pattern signature matching for hardware network intrusion detection systems,” in IEEE Globecom 2005, November-December 2005.) such as TCAMs, SRAMs or both. The former is more expensive and consumes more power, while the latter suffers from speed limitation. Other approaches implement the DPI on a single-chip (most of the time on a single FPGA). The first generation of the single-chip solutions (J. Moscola, J. Lockwood, R. P. Loui, and M. P., “Implementation of a content-scanning module for an internet firewall.” in FCCM, 2003, pp. 31-38.); (C. Clark and D. Schimmel, “Scalable pattern matching for highspeed networks,” in IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), Napa, Calif., 2004, pp. 249-257.); (Y. H. Cho and W. H. Mangione-Smith, “Fast reconfiguring deep packet filter for 1+ gigabit network.” in FCCM, 2005, pp. 215-224.); Z. K. Baker and V. K. Prasanna, “High-throughput Linked-Pattern Matching for Intrusion Detection Systems,” in Proceedings of the First Annual ACM Symposium on Architectures for Networking and Communications Systems, 2005.); and (N. Tuck, T. Sherwood, B. Calder, and G. Varghese, “Deterministic memory-efficient string matching algorithms for intrusion detection,” in Proc. of the 2004 IEEE Infocom Conference, 2004.), with the exception of (N. Tuck, T. Sherwood, B. Calder, and G. Varghese, “Deterministic memory-efficient string matching algorithms for intrusion detection,” in Proc. of the 2004 IEEE Infocom Conference, 2004.), tailor string matching circuits to the input set. Although it is high-speed, it requires hardware reconfiguration for updates.
A recent proposal (I. Sourdis, D. Pnevmatikatos, S. Wong, and S. Vassiliadis, “A reconfigurable perfect-hashing scheme for packet inspection,” in Proc. 15th International Conference on Field Programmable Logic and Applications (FPL 2005), August 2005, pp. 644-647.) takes a hybrid approach, using reconfigurable circuits and on-chip memory. The approach in (I. Sourdis, D. Pnevmatikatos, S. Wong, and S. Vassiliadis, “A reconfigurable perfect-hashing scheme for packet inspection,” in Proc. 15th International Conference on Field Programmable Logic and Applications (FPL 2005), August 2005, pp. 644-647.) use perfect hashing (though not minimal perfect hashing), but requires reconfiguration and has less than 100% signature memory utilization due to using perfect hashing rather than minimal perfect hashing. In (Y. Lu, B. Prabhakar, and F. Bonomi, “Perfect hashing for network applications,” in IEEE Symposium on Information Theory), Seattle, Wash., 2006, pp. 2774-2778.), a minimal perfect hashing scheme is provided with O(η) space complexity and low construction time. This approach, however, requires a complex addressing scheme, where additional logic is required to calculate the address in the hash table, to locate the signature for an exact match. Other recent proposals such as (N. Tuck, T. Sherwood, B. Calder, and G. Varghese, “Deterministic memory-efficient string matching algorithms for intrusion detection,” in Proc. of the 2004 IEEE Infocom Conference, 2004.), (L. Tan and T. Sherwood, “Architectures for bit-split string scanning in intrusion detection,” IEEE Micro, January-February 2006.), (G. Papadopoulos and D. N. Pnevmatikatos, “Hashing+memory=low cost, exact pattern matching.” in Proc. 15th International Conference on Field Programmable Logic and Applications (FPL), August 2005, pp. 3944.) also use on-chip memory for signature-specific data and for avoiding hardware reconfiguration for updates.
The pioneering work on single-chip methods without reconfiguration for signature updates (N. Tuck, T. Sherwood, B. Calder, and G. Varghese, “Deterministic memory-efficient string matching algorithms for intrusion detection,” in Proc. of the 2004 IEEE Infocom Conference, 2004.) set the stage by modifying the classical Aho-Corasick String Matching Algorithm (A. Aho and M. J. Corasick, “Efficient string matching: an aid to bibliographic search,” Communications of the ACM, vol. 18, no. 6, pp. 333-340, 1975.) for hardware implementation. Authors in (L. Tan and T. Sherwood, “Architectures for bit-split string scanning in intrusion detection,” IEEE Micro, January-February 2006.) use small state machines to further improve memory requirements and fit the entire Snort ([Online]. Available: http://Hwww.snort.org) signature database to 0.4 MB memory. It is claimed that it can run at 10 Gbps with an ASIC implementation. It is noteworthy that the ASIC-based solution has a technology advantage over other proposals, most of which are FPGA-based. Authors in (H.-J. Jung, Z. K. Baker, and V. K. Prasanna, “Performance of FPGA Implementation of Bit-split Architecture for Intrusion Detection Systems,” in Proceedings of the Reconfigurable Architectures Workshop at IPDPS (RAW '06), 2006.) later showed that FPGA implementation of (L. Tan and T. Sherwood, “Architectures for bit-split string scanning in intrusion detection,” IEEE Micro, January-February 2006.) can achieve lower throughput while using larger memory. Authors in (G. Papadopoulos and D. N. Pnevmatikatos, “Hashing+memory=low cost, exact pattern matching.” in Proc. 15th International Conference on Field Programmable Logic and Applications (FPL), August 2005, pp. 3944.) use a sparse hash table to store signatures so that the hash collisions are minimized or, more likely, eliminated. Although the authors use indirection to improve memory utilization, it is still lower than many other proposals. In addition, the authors use glue logic to detect long patterns, which may require reconfiguration for signature updates.
Since most of the incoming packets are legitimate, running DPI for every single byte of an incoming packet is overkill. Methods exploring this property of intrusion detection were proposed to skip most of the legitimate packets through simple and fast pre-processing (K. Anagnostakis, S. Antonatos, E. Markatos, and M. Polychronakis, “E2xb: A domain-specific string matching algorithm for intrusion detection,” in Proc. of the 18th IFIP International Information Security Conference, 2003.); (S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood, “Deep packet inspection using parallel bloom filters,” in Symposium on High Performance Interconnects (HotI), Stanford, Calif., August 2003, pp. 44-51.); (H. Song, T. Sproull, M. Attig, and J. Lockwood, “Snort offloader: A reconfigurable hardware nids filter,” in 15th International Conference on Field Programmable Logic and Applications (FPL 2005), Tampere, Finland, August 2005.), thus significantly reducing the string matching operation that allows few queries before attempting any string matching. However, these methods still require additional full string matching for suspicious data, and do not improve the worst-case performance.
Each of the foregoing articles (in this section 1.2.1) is incorporated herein by reference.